package hot100;

import 蓝桥杯十二.D;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/24 15:19
 */
public class lc103二叉树的矩形遍历 {



    // 你他妈 debug 半天 ,发现是  二叉护树的层序遍历写的有问题!
    public List<List<Integer>> solve(TreeNode root){
        List<List<Integer>> ans = new ArrayList<>();
        boolean flag = true; // flag 等于true 表示从  <-----   false ------>
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        ans.add(Arrays.asList(root.val));
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.removeFirst();
                if(treeNode.left !=null){
                    queue.add(treeNode.left);
                    path.add(treeNode.left.val);
                }
                if(treeNode.right != null){
                        queue.add(treeNode.right);
                        path.add(treeNode.right.val);
                    }
            }
            if(path.size() == 0){
                continue;
            }
            if(flag){
                Collections.reverse(path);
            }
            flag = flag ? false : true;
            ans.add(new ArrayList<>(path));
        }

        return ans;
    }


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
